package com;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.SimpleWeightedGraph;

public class TSRanInsertion {
	
	/*This method uses the random insertion method algorithm to solve TS.*/
	
	static double compute(SimpleWeightedGraph<Node, DefaultWeightedEdge> graph) {
		 
		//Initialise minDist to zero.
		double minDist = 0.0;
		
		//HashSet offers constant-time performance on the 'contains' operation, the only one we need.
		HashSet<Node> visitedNodes = new HashSet<Node>();
		
		//Get all nodes in the graph.
		Set<Node> vertices = graph.vertexSet();
		
		//Pick any vertex and set it as the first node of the tour.
		Iterator<Node> iterN = vertices.iterator();
		Node firstNode = iterN.next();
		
		//Pick another vertex and set it as the last node of the tour.
		Node lastNode = iterN.next();
		
		//Mark them both as visited.
		visitedNodes.add(firstNode);
		visitedNodes.add(lastNode);
		
		//Add the weight of the edge connecting these two nodes to the answer.
		minDist += graph.getEdgeWeight(graph.getEdge(firstNode, lastNode));
		
		//Iterate through the vertices.
		while (visitedNodes.size() < vertices.size()) {
						//Get the next vertex.							   
						Node activeNode = iterN.next();
						//Calculate its distance to the first and last nodes of route.
						double distToFirst = graph.getEdgeWeight(graph.getEdge(activeNode, firstNode));
						double distToLast = graph.getEdgeWeight(graph.getEdge(activeNode, lastNode));
						//Add the vertex to the end or start of the route, depending on where it causes 
						//the least increase to the length of the tour. Also add the weight to the answer.
						if (distToFirst <= distToLast) {minDist += distToFirst;
													   	firstNode = activeNode;}
						else {minDist += distToLast;
							  lastNode = activeNode;}
						//Mark the vertex as visited.
						visitedNodes.add(activeNode);
		}
		//We are at the last vertex now so add the weight of the edge connecting the
		//first and last nodes of the tour to the answer.
		minDist += graph.getEdgeWeight(graph.getEdge(firstNode, lastNode));
		
		return minDist;
		
	}
								
										
										
}
